//
//  239. 滑动窗口最大值.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/10.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution239_2 {
    // 滑动窗口的最大值
    // 保持队列是单调的。队列的出口就是最大的值
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        guard k > 0 else {
            return []
        }
        var queue: [Int] = []
        var result: [Int] = []
        for i in 0..<nums.count {
            // 维护单调队列
            while !queue.isEmpty,
                  let top = queue.last,
                  nums[top] <= nums[i] {
                queue.removeLast()
            }
            // 入队
            queue.append(i)
            
            // 判定队列首元素是否有效
            if let first = queue.first, first <= i - k {
                queue.removeFirst()
            }
            if i >= k - 1 {
                result.append(nums[queue.first!])
            }
        }
        return result
    }
    
    static func test() {
        // 加入这是解析语法树得到的一个表达式
        //        let nums = [1,3,-1,-3,5,3,6,7]
        let nums = [1,-1]
        let k = 1
        let solution = Solution239_2()
        let result = solution.maxSlidingWindow(nums, k)
        print(result)
    }
}
